#ifndef _H_AC
#define _H_AC

#include <map>
#include <iterator>
#include <queue>
#include <utility>
//#include <algorithm>

using namespace std;

template <typename T>
struct TrieNode{
	TrieNode():fail(NULL),is_word(false){}
	map<T,TrieNode<T>*> child_node;
	TrieNode* fail;
	bool is_word;
	int height; 
};

template <typename T>
class AC {
	public:
		AC(){
			__root = new TrieNode<T>();
			__root->fail = __root;
			__root->height = 0;
			__need_adjust = true;
		}
		template <typename Iterator>
		bool insert(Iterator first,Iterator last);
		template <typename Container>
		bool insert(const Container& c){
			insert(c.begin(),c.end());
		}


		template <typename Iterator>
		pair<Iterator,Iterator> match(Iterator first,Iterator last); 
		template <typename Iterator>
		bool search(Iterator first,Iterator last);
		template <typename Container>
		bool search(const Container& c){
			search(c.begin(),c.end());

		}
		bool walk(); //测试用，用来遍历字典树

	private:
		void adjust();
		TrieNode<T>* __root;
		bool __need_adjust;
};

#include "ac-inl.h"
#endif
